﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BitOperations
{
    /* Problem description
     * 
     * Given an array of integers, print out the power sets of the array
     * For example, given {1, 2, 3}
     * shoud print out {} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
     * 
     */ 

    class PowerSetUsingBit
    {
        /* algorithm
         * 
         * treat it as binary representation
         * 000 001 010 011 100 101 110 111
         * if there is a "1" in the position, print out the arr[i]
         */

        public void PowerSet(int[] arr)
        {
            int number_of_element = 1 << arr.Length; // there are 2^(Arr.length) elments
            int index_of_element = 0;
            int bit_mask = 0;
            int index_in_element = 0;

            for (index_of_element = 0; index_of_element < number_of_element; index_of_element++)
            {
                Console.Write(" { ");

                for (bit_mask = index_of_element, index_in_element = 0; bit_mask > 0; ++index_in_element)
                {
                    if ((bit_mask & 1) > 0) // means the specific bit is one, we should print out this element
                        Console.Write("{0} ", arr[index_in_element]);

                    bit_mask = bit_mask >> 1;
                }

                Console.WriteLine(" }");
            }
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 3, 4 };
            PowerSetUsingBit psb = new PowerSetUsingBit();

            psb.PowerSet(arr);
            Console.WriteLine("Press any key to finish...");
            Console.ReadKey();
        }
    }
}
